An Airline Scheduling and Routing (ASR) problem is a problem faced by an airline in creating flight schedules for a single heterogeneous aircraft fleet. A flight schedule can include a sequence of flights to be flown by a single aircraft (i.e., routing) and the departure and arrival times for each flight leg (i.e., scheduling). An efficient and cost-effective solution to the ASR problem may be extremely critical to the airline, since a given schedule determines a significant portion of the airline's overall cost including the fixed cost for each aircraft, fuel cost, maintenance costs, and the cost of crew members assigned to operate the airline's final flight schedule.
Given that the airline has a fixed number of aircraft to operate at any given time and that the fixed cost for adding and operating additional aircraft is very high, it is imperative that the airline utilize its existing aircraft resources in the most efficient manner. Since different flight schedules result in varying costs and revenues to the airline, substantial cost reductions and revenue increases can be obtained by generating optimal or near-optimal aircraft schedules. However, due to the extremely large number of possible flight schedules and the numerous operational and regulatory restrictions that must be enforced, the ASR problem is a highly complex problem that requires the use of sophisticated mathematical modeling and solution algorithms in order to produce optimal solutions.